package com.study;

import java.util.Arrays;

/**
 * @program: leetcode
 * @author: jzhou
 * @date: 2022-11-13 13:43
 * @version: 1.0
 * @description: 将两个有序数组合并成一个有序数组
 **/
public class MergeSortArray {
    public static void main(String[] args) {
        int[] arr1 = {1,3,5,7,10,11};
        int[] arr2 = {2,4,6,8,9};
        System.out.println(Arrays.toString(mergeSortArray(arr1,arr1.length,arr2,arr2.length)));
        int[] arr3 = {1,3,5,7,10,11,0,0,0,0,0};
        mergeSortArray2(arr3,6,arr2,arr2.length);
        System.out.println(Arrays.toString(arr3));
    }

    // 使用尾插法，倒叙插入，这样可以不使用额外数组
    private static void mergeSortArray2(int[] arr3, int m, int[] arr2, int n) {
        //定义指针
        int p3 = m - 1 ;// arr3 指针
        int p2 = n - 1 ;// arr2 指针
        int p = m + n - 1 ;// 新数组 指针

        while (p3 >=0 && p2 >= 0){
            arr3[p--] = arr3[p3] > arr2[p2] ? arr3[p3--] : arr2[p2--];
        }
        if (p2 > 0){
            System.arraycopy(arr2,0,arr3,0,p2 + 1);
        }
    }

    // 双指针 正向插入 解法
    private static int[] mergeSortArray(int[] arr1, int m, int[] arr2, int n) {
        int[] new_arr = new int[m + n];
        //定义指针
        int p1 = 0 ;// arr1 指针
        int p2 = 0 ;// arr2 指针
        int p = 0 ;// 新数组 指针

        while (p1 < m && p2 < n){
            new_arr[p++] = arr1[p1] > arr2[p2] ? arr2[p2++] : arr1[p1++];
        }
        if (p1 < m){//arr1 有剩余直接copy到新数组
            System.arraycopy(arr1,p1 ,new_arr,p1 + p2,m - p1);
        }
        if (p2 < n){//arr1 有剩余直接copy到新数组
            System.arraycopy(arr2,p2,new_arr,p1 + p2,n - p2);
        }
        return new_arr;
    }

    private static int[] mergeSortArray3(int[] arr1, int m, int[] arr2, int n){
        int[] new_arr = new int[m+n];
        //定义指针
        int p = 0,p1 = 0, p2 = 0;
        while (p1 < m && p2 < n){
            new_arr[p++] = arr1[p1] > arr2[p2] ? arr2[p2++] : arr1[p1++];
        }
        if(p1 < m){
            System.arraycopy(arr1,p1,new_arr,p1+p2,m-p1+1);
        }
        if(p2 < n){
            System.arraycopy(arr2,p2,new_arr,p1+p2,n-p2+1);
        }
        return new_arr;
    }
}
